<!DOCTYPE html>
<html lang="zh">

<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>
    
    数组和广义表 - DSRBLOG
    
  </title>
  

  
  
  <link href="atom.xml" rel="alternate" title="DSRBLOG" type="application/atom+xml">
  <link rel="stylesheet" href="asset/css/style.min.css">
  <link rel="stylesheet" href="asset/css/doc.css">
  <script src="asset/app.js"></script>


</head>

<body> <section class="ct-body">
	<div class="container">
		<div class="columns is-variable bd-klmn-columns is-4 is-centered">
			<div class="column is-four-fifths">
				<div class="post-body single-content">
					
					<h1 class="title">
						数组和广义表
					</h1>


					<div class="media">
						
						
						<div class="media-content">
							<div class="content">
								<p>
									<span class="date">2022/03/13 19:31 下午</span>
									

									

									<br />
									<span class="tran-tags">Tags:</span>&nbsp;
									
									<a class="tag is-link is-light">#数据结构与算法</a>
									

								</p>
							</div>
						</div>

					</div>
				</div>
				<article class="markdown-body single-content">
					<h2><a id="%E6%95%B0%E7%BB%84%E7%9A%84%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数组的定义</h2>
<p>由一组名字相同、下标不同的变量构成</p>
<p>高级语言中的数组是顺序结构；而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择</p>
<h3><a id="%E4%B8%80%E7%BB%B4%E6%95%B0%E7%BB%84%E7%9A%84%E7%89%B9%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>一维数组的特点</h3>
<p>只有1个下标，<strong>a<sub>i</sub></strong> 是<strong>a<sub>i+1</sub></strong> 的直接前驱</p>
<h3><a id="%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E7%9A%84%E7%89%B9%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>二维数组的特点</h3>
<p>有2个下标，每个元素<strong>a<sub>i,j</sub></strong> 受到两个关系（行关系和列关系）的约束</p>
<p>一个n维数组可以看成是由若干个<code>n - 1</code>维数组组成的线性表</p>
<h2><a id="%E6%95%B0%E7%BB%84%E7%9A%84%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%A4%BA%E5%92%8C%E5%AE%9E%E7%8E%B0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数组的顺序表示和实现</h2>
<ul>
<li>计算机的存储结构是一维的，而数组一般是多维的，需要事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中</li>
<li>在二维数组中，我们既可以规定按行存储，也可以规定按列存储</li>
</ul>
<h3><a id="%E8%AE%A1%E7%AE%97%E6%95%B0%E7%BB%84%E5%85%83%E7%B4%A0%E5%9C%B0%E5%9D%80" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>计算数组元素地址</h3>
<p><img src="media/16471711070028/16471847533684.jpg" alt="" /></p>
<h4><a id="%E8%A1%8C%E4%BC%98%E5%85%88" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>行优先</h4>
<p>LOC(a<sub>i,j</sub>) = LOC(a<sub>c1,c2</sub>)<strong><sup>[1]</sup></strong> + [(i - c<sub>1</sub>)<strong><sup>[2]</sup></strong> * (d<sub>2</sub> - c<sub>2</sub> + 1)<strong><sup>[3]</sup></strong> + (j - c<sub>2</sub>)]<strong><sup>[4]</sup></strong> * L <strong><sup>[5]</sup></strong></p>
<h5><a id="%E6%B3%A8%E9%87%8A%EF%BC%9A" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>注释：</h5>
<p><strong>[1]：</strong> 数组基址<br />
<strong>[2]：</strong> a<sub>i,j</sub>之前的行数<br />
<strong>[3]：</strong> 总列数，即第2维的长度<br />
<strong>[4]：</strong> a<sub>i,j</sub>本行之前的元素个数<br />
<strong>[5]：</strong> 单个元素长度</p>
<p>即：(所在行之前的行数 * 每行的总列数 * 所在行之前的元素个数) * 元素长度</p>
<h4><a id="%E5%88%97%E4%BC%98%E5%85%88" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>列优先</h4>
<p>LOC(a<sub>i,j</sub>) = LOC(a<sub>c1,c2</sub>)<strong><sup>[1]</sup></strong> + [(j - c<sub>2</sub>)<strong><sup>[2]</sup></strong> * (d<sub>1</sub> - c<sub>1</sub> + 1)<strong><sup>[3]</sup></strong> + (i - c<sub>1</sub>)]<strong><sup>[4]</sup></strong> * L <strong><sup>[5]</sup></strong></p>
<h5><a id="%E6%B3%A8%E9%87%8A%EF%BC%9A" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>注释：</h5>
<p><strong>[1]：</strong> 数组基址<br />
<strong>[2]：</strong> a<sub>i,j</sub>之前的列数<br />
<strong>[3]：</strong> 总行数，即第1维的长度<br />
<strong>[4]：</strong> a<sub>i,j</sub>本列之前的元素个数<br />
<strong>[5]：</strong> 单个元素长度</p>
<p>即：(所在列之前的列数 * 每列的总行数 * 所在列之前的元素个数) * 元素长度</p>
<h2><a id="%E7%9F%A9%E9%98%B5%E7%9A%84%E5%8E%8B%E7%BC%A9%E5%AD%98%E5%82%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>矩阵的压缩存储</h2>
<h4><a id="%E4%BB%80%E4%B9%88%E6%98%AF%E5%8E%8B%E7%BC%A9%E5%AD%98%E5%82%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>什么是压缩存储</h4>
<p>若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间</p>
<h4><a id="%E4%BB%80%E4%B9%88%E6%A0%B7%E7%9A%84%E7%9F%A9%E9%98%B5%E5%85%B7%E5%A4%87%E5%8E%8B%E7%BC%A9%E6%9D%A1%E4%BB%B6" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>什么样的矩阵具备压缩条件</h4>
<p>稀疏矩阵和特殊矩阵（对称矩阵、对角矩阵、三角矩阵）</p>
<h4><a id="%E4%BB%80%E4%B9%88%E5%8F%AB%E7%A8%80%E7%96%8F%E7%9F%A9%E9%98%B5" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>什么叫稀疏矩阵</h4>
<p>矩阵中非零元素的个数较少（一般小于5%）</p>
<h3><a id="%E5%AF%B9%E7%A7%B0%E7%9F%A9%E9%98%B5" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>对称矩阵</h3>
<ul>
<li>
<p>n阶对称矩阵满足：a<sub>ij</sub> == a<sub>ji</sub></p>
</li>
<li>
<p>可以将n<sup>2</sup>个元素压缩存储到<code>n(n + 1) / 2</code>个空间中</p>
</li>
<li>
<p>假设以一维数组<code>sa[n(n + 1)]/2]</code>作为n阶对称矩阵的存储结构，则<code>sa[k]</code>和矩阵元素a<sub>ij</sub>的对应关系为：<br />
<img src="media/16471711070028/16472473284672.jpg" alt="" /></p>
</li>
<li>
<p>对所有的k都能确定<code>sa[k]</code>中元在矩阵中位置(i, j)<br />
<img src="media/16471711070028/16472475376718.jpg" alt="" /></p>
</li>
</ul>
<h3><a id="%E7%A8%80%E7%96%8F%E7%9F%A9%E9%98%B5" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>稀疏矩阵</h3>
<p>对每个非零元素增开若干存储单元，存放在其所在的行号和列号，即可准确反映该元素所在位置</p>
<h4><a id="%E5%AE%9E%E7%8E%B0%E6%96%B9%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>实现方法</h4>
<p>将每个非零元素用一个三元组(i, j ,a<sub>ij</sub>)来表示，则每个稀疏矩阵可用一个三元组表来表示</p>
<h5><a id="%E4%B8%89%E5%85%83%E7%BB%84%E8%A1%A8%E7%9A%84%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E8%A1%A8%E7%A4%BA" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>三元组表的顺序存储表示</h5>
<pre class="line-numbers"><code class="language-c">#define MAXSIZE 125000 //设非零元素最大个数为125000
typedef int ElemType;

//三元组表单个结点的定义
typedef struct
{
    int i;      //元素行号
    int j;      //元素列号
    ElemType e; //元素值
} Triple;

//整个三元组表的定义
typedef struct
{
    //三元组表，以行为主序存入一维向量data[]中
    Triple data[MAXSIZE + 1];

    int mu; //矩阵总行数
    int nu; //矩阵总列数
    int tu; //矩阵中非零元素个数
} Maxtrix;
</code></pre>
<h5><a id="%E4%B8%89%E5%85%83%E7%BB%84%E8%A1%A8%E7%9A%84%E5%9B%BE%E7%A4%BA" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>三元组表的图示</h5>
<p><img src="media/16471711070028/16472478421137.jpg" alt="" /><br />
上图所示稀疏矩阵的压缩存储形式如下：</p>
<table>
<thead>
<tr>
<th>i</th>
<th>j</th>
<th>value</th>
<th>注释</th>
</tr>
</thead>
<tbody>
<tr>
<td>6</td>
<td>6</td>
<td>8</td>
<td>存储原矩阵的行、列、非零元素个数</td>
</tr>
<tr>
<td>1</td>
<td>2</td>
<td>12</td>
<td>第n行、第n列、非零元素值</td>
</tr>
<tr>
<td>1</td>
<td>3</td>
<td>9</td>
<td></td>
</tr>
<tr>
<td>3</td>
<td>1</td>
<td>-3</td>
<td></td>
</tr>
<tr>
<td>3</td>
<td>5</td>
<td>14</td>
<td></td>
</tr>
<tr>
<td>4</td>
<td>3</td>
<td>24</td>
<td></td>
</tr>
<tr>
<td>5</td>
<td>2</td>
<td>18</td>
<td></td>
</tr>
<tr>
<td>6</td>
<td>1</td>
<td>15</td>
<td></td>
</tr>
<tr>
<td>6</td>
<td>4</td>
<td>-7</td>
<td></td>
</tr>
</tbody>
</table>
<h2><a id="%E5%B9%BF%E4%B9%89%E8%A1%A8%E7%9A%84%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>广义表的定义</h2>
<p>广义表是线性表的推广，也称为列表（lists）<br />
<img src="media/16471711070028/16472511729688.jpg" alt="" /></p>
<p>在广义表中约定：</p>
<ul>
<li>第一个元素是表头，而其余元素另外组成一个表，称为表尾</li>
<li>用小写字母表示原子类型，用大写字母表示列表</li>
<li>广义表中元素既可以是原子类型，也可以是列表，当每个元素都为原子且类型相同时，就是线性表</li>
</ul>
<h3><a id="%E5%B9%BF%E4%B9%89%E8%A1%A8%E7%9A%84%E7%89%B9%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>广义表的特点</h3>
<ul>
<li>有次序性，拥有一个直接前驱和一个直接后继</li>
<li>长度 = 表中元素个数（只包含最外层括号内的元素，如C = (a, (b, c, d))的长度为2）</li>
<li>深度 = 表中括号的重数</li>
<li>可递归：自己可以作为自己的子表</li>
<li>可共享：可以为其它广义表所共享</li>
<li>任意一个非空广义表，表头可能是原子，也可能是列表，但表尾一定是列表</li>
</ul>
<h4><a id="%E4%BE%8B" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>例</h4>
<table>
<thead>
<tr>
<th>广义表</th>
<th>长度</th>
<th>深度</th>
<th>解释</th>
</tr>
</thead>
<tbody>
<tr>
<td>A = ()</td>
<td>0</td>
<td>1</td>
<td></td>
</tr>
<tr>
<td>B = (e)</td>
<td>1</td>
<td>1</td>
<td></td>
</tr>
<tr>
<td>C = (a, (b, c, d))</td>
<td>2</td>
<td>2</td>
<td></td>
</tr>
<tr>
<td>D = (A, B, C)</td>
<td>3</td>
<td>3</td>
<td>C的深度为2</td>
</tr>
<tr>
<td>E = (a, E)</td>
<td>2</td>
<td>无穷</td>
<td>E本身递归</td>
</tr>
</tbody>
</table>
<h3><a id="%E5%B9%BF%E4%B9%89%E8%A1%A8%E7%9A%84%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>广义表的基本操作</h3>
<h4><a id="gethead-l" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>GetHead(L)</h4>
<p>取表头，可能是原子或列表</p>
<h4><a id="gettail-l" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>GetTail(L)</h4>
<p>取表尾，一定是列表</p>
<h2><a id="%E5%B9%BF%E4%B9%89%E8%A1%A8%E7%9A%84%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>广义表的存储结构</h2>

				</article>
				<div class="comments-wrap">
					<div class="share-comments">
						

						

						
					</div>
				</div><!-- end comments wrap -->
			</div>
		</div><!-- end columns -->
	</div><!-- end container -->
</section>  














<script src="asset/prism.js"></script>









</body>

</html>